public class test {
    public static int maxSubArray(int[] nums) {
        //贪心算法：计算sum和maxsubarray
        if(nums.length == 1){
            return nums[0];
        }
        int maxSubArray = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.length; i++){
            //sum要想有资格继续壮大 就必须大于 0 否则还不如恢复0
            sum = Math.max(sum,0);
            sum += nums[i];
            //maxSubArray始终取最大值
            maxSubArray = Math.max(sum,maxSubArray);
        }
        return maxSubArray;
    }
}

//动态规划： 每一个元素看前一个元素是否>0。大于0，两者之和为新的元素，依次向后覆盖数组
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int temp=nums[0];
        for(int i=1;i<nums.length;i++){
            if(temp>0) nums[i]+=temp;
            temp=nums[i];
        }
        int max=nums[0];
        for(int i=0;i<nums.length;i++)
            if(nums[i]>max) max=nums[i];

        return max;
    }
}

